import collections


# 深度优先搜索
# class Solution(object):
#     def validTree(self, n, edges):
#         """
#         :type n: int
#         :type edges: List[List[int]]
#         :rtype: bool
#         """
#         if n == 1:
#             return True
#         p = [0] * n
#         d = collections.defaultdict(set)
#         for item in edges:
#             d[item[0]].add(item[1])
#             d[item[1]].add(item[0])
#
#         def search(index):
#             if index in d:
#                 p[index] += 1
#                 for next_index in d[index]:
#                     if p[next_index] == 0:
#                         d[next_index].remove(index)
#                         search(next_index)
#                     else:
#                         p[next_index] += 1
#         search(0)
#         for i in range(n):
#             if p[i] != 1:
#                 return False
#         return True

# 并查集
class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        root = [i for i in range(n)]

        def find(x):
            while root[x] != x:
                x = root[x]
            return x

        for item in edges:
            x = find(item[0])
            y = find(item[1])
            if x == y:
                return False
            else:
                d = min(x, y)
                root[item[0]] = d
                root[item[1]] = d
                root[x] = d
                root[y] = d

        for i in range(n):
            root[i] = find(i)
        d = root[0]
        for i in range(1, n):
            if root[i] != d:
                return False
        return True


data = Solution()
n = 4
edges = [[0, 1], [2, 3], [1, 2]]
print(data.validTree(n, edges))
